1. Field of the Invention
This invention relates to circuits and methods for quickly identifying an object in a sequential list, and particularly relates to circuits and methods for selecting operations for use by execution units in a superscalar processor.
2. Description of Related Art
A typical computer program is a list of instructions which when compiled or assembled generates a sequence of machine instructions or operations which a processor executes. The operations have a program order defined by the logic of the computer program and are generally intended for sequential execution in the program order. Scalar processors execute the operations in the program order which limits a scalar processor to completing one operation before completing the next operation. To improve processor performance, superscalar processors have been developed which contain a variety of execution units which are capable of operating in parallel so that operations can be executed and completed in parallel or out of the program order. Superscalar processors can complete more than one operation at a time and therefore can be computationally faster than scalar processors operating at the same clock speed.
A scheduler in a superscalar processor may schedule execution of operations so that operations are executed out of the normal program order. Difficulties in out-of-order execution arise because one operation may depend on another in that the logic of a computer program requires that the first operation in the program be executed before the second operation. Whether an operation should be executed at all often depends on the result of a branch operation. If an operation that follows a conditional branch operation is executed before the branch, the execution must be speculative because the branch may skip over the instruction. Additionally, many computers require that a system's state be known just before or after an operation generates an error, interrupt, or trap; but when operations are executed out of order, an operation which follows an error in a program may have been executed before the error occurred. Thus, the processor must be able to undo operations which should not have been executed and must be able to construct the system's state following an error.
Two somewhat conflicting goals of superscalar architecture are quick scheduling so that a processor can operate at a high clock rate and efficient scheduling to maximize parallel execution of operation which are actually required for completion of the program. Schedulers which accomplish these goals are desired.